#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <sys/time.h>
#include <string.h>
#include "graph.h"
#include "euler.h"
#include "common.h"
#include "prim.h"

// uzywaj algorytmu Prim'a zamiast Dijkstry
#define PRIM 1






typedef struct {
	int		numNodes;
	int		offset;
	int		numTODO;
	byte*	nodes;
	Graph*	graph;
} NodeQueue;



NodeQueue NodeQueue_new(int startNode, int endNode, Graph* graph) {
	NodeQueue	res;
	int				i;
	
	res.offset = startNode;
	res.numNodes = endNode - startNode;
	res.numTODO = 0;
	res.nodes		= new(byte, res.numNodes);
	res.graph = graph;
	
	for (i = startNode; i < endNode; ++i) {
		res.nodes[i - res.offset] = -1;
	}
	
	return res;
}


void NodeQueue_top(NodeQueue* nq, int* node, double* dist) {
	int i, ni;
	
	assert (node != null);
	assert (dist != null);
	
	*node = -1;
	*dist = dist_max;
	
	if (0 == nq->numTODO) return;
	
	for (i = 0; i < nq->numNodes; ++i) {
		if (-1 == nq->nodes[i]) continue;
		ni = i + nq->offset;
		
		if (nq->graph->dists[ni] < *dist) {
			*dist = nq->graph->dists[ni];
			*node = ni;
		}
	}
}


void NodeQueue_remove(NodeQueue* nq, int node) {
	int offset = nq->offset;
	
	assert (node-offset >= 0 && node-offset < nq->numNodes);
	nq->nodes[node-offset] = -1;
	--nq->numTODO;
}


void NodeQueue_insert(NodeQueue* nq, int node, int dist) {
	int offset = nq->offset;
	assert (node-offset >= 0 && node-offset < nq->numNodes);
	
	nq->nodes[node-offset] = 1;
	nq->graph->dists[node] = dist;
	
	++nq->numTODO;
}





void relaxGraph(NodeQueue* nq, Graph graph, int node_, int dist, int startNode, int endNode) {
	int i, conI;
	
	assert (nq != null);	
	assert (node_ < graph.numNodes && node_ >= 0);
	
	Node* node = &graph.nodes[node_];
	
#if PRIM == 1
	// duza ujemna wartosc oznaczajaca brak jakotakiej odleglosci
	graph.dists[node_] = -dist_max;
#endif
	
	for (i = 0; i < node->numConns; ++i) {
		conI = node->conns[i];

		assert (conI >= startNode && conI < endNode);

#if PRIM == 1
		if (node->connDists[i] < graph.dists[conI]) {
			graph.prev[conI] = node_;
			graph.dists[conI] = node->connDists[i];
			NodeQueue_insert(nq, conI, graph.dists[conI]);
		}
#else
		if (node->connDists[i] + dist < graph.dists[conI]) {
			graph.prev[conI] = node_;
			graph.dists[conI] = node->connDists[i] + dist;
			NodeQueue_insert(nq, conI, graph.dists[conI]);
		}
#endif
	}
}


typedef struct {
	double	dist;
	int		node;
} NodeDist;


uint64 processDijkstra(Graph graph, int sourceNode, int rank, int numProc) {
	struct timeval	timeVal;
	uint64				timeL = 0;
	
	#define TIME_START		gettimeofday(&timeVal, null); timeL -= timeVal.tv_sec * 1000000 + timeVal.tv_usec;
	#define TIME_END			gettimeofday(&timeVal, null); timeL += timeVal.tv_sec * 1000000 + timeVal.tv_usec;
	
	NodeQueue		localQueue;
	int					startNode, endNode;
	int					i, bestNode, bestDist;
	NodeDist			localMinNode, minNode;
	int					*recvSiz = null, *recvOff = null;
	
	startNode	= (rank+0) * graph.numNodes / numProc;
	endNode	= (rank+1) * graph.numNodes / numProc;
	
	
	localQueue = NodeQueue_new(startNode, endNode, &graph);
	
	if (sourceNode >= startNode && sourceNode < endNode) {
		NodeQueue_insert(&localQueue, sourceNode, 0);
	}


	TIME_START;
	
	for (i = 0; i < graph.numNodes; ++i) {
		NodeQueue_top(&localQueue, &localMinNode.node, &localMinNode.dist);
		
		
		TIME_END;		// wyklucz czas komunikacji
			MPI_Allreduce(&localMinNode, &minNode, 1, MPI_DOUBLE_INT, MPI_MINLOC, MPI_COMM_WORLD);
		TIME_START;
		
		
		bestDist = minNode.dist;
		bestNode = minNode.node;
		
		if (dist_max == bestDist) {
			break;
		}
		
		assert (-1 != bestNode);
		
		if (bestNode == localMinNode.node) {
			NodeQueue_remove(&localQueue, bestNode);
		}
		
		relaxGraph(&localQueue, graph, bestNode, bestDist, startNode, endNode);
	}

	TIME_END;

	
	/* dane dla MPI_Gatherv */
	if (0 == rank) {
		recvSiz = new(int, numProc);
		recvOff = new(int, numProc);
		
		for (i = 0; i < numProc; ++i) {
			recvOff[i] = (i+0) * graph.numNodes / numProc;
			recvSiz[i] = (i+1) * graph.numNodes / numProc - recvOff[i];
		}
	}
	
	/* odbierz odleglosci */
	MPI_Gatherv(
			graph.dists + startNode, endNode-startNode, MPI_DOUBLE,
			graph.dists, recvSiz, recvOff, MPI_DOUBLE,
			0,
			MPI_COMM_WORLD);

	/* odbierz poprzednikow */
	MPI_Gatherv(
			graph.prev + startNode, endNode-startNode, MPI_INT,
			graph.prev, recvSiz, recvOff, MPI_INT,
			0,
			MPI_COMM_WORLD);


	if (0 == rank) {
		free(recvSiz);
		recvSiz = null;
		free(recvOff);
		recvOff = null;
	}

	return timeL;
}


